/* 646. 最长数对链 */
/**
 * @param {number[][]} pairs
 * @return {number}
 */
/*

    动态规划
    定义dp[i] 为以pairs[i]为结尾的最长数对链的长度    
*/
var findLongestChain = function (pairs) {
	const n = pairs.length
	pairs.sort((a, b) => a[0] - b[0])
	const dp = new Array(n).fill(1)
	for (let i = 0; i < pairs.length - 1; i++) {
		for (let j = 0; j < i; j++) {
			if (pairs[i][0] > pairs[j][1]) {
				dp[i] = Math.max(dp[i], dp[j] + 1)
			}
		}
	}
	return dp[n - 1]
}
/* 贪心+二分 */
var findLongestChain = function (pairs) {
	pairs.sort((a, b) => a[0] - b[0])
	const arr = []
	for (const p of pairs) {
		let x = p[0],
			y = p[1]
		if (!arr.length || x > arr[arr.length - 1]) {
			arr.push(y)
		} else {
			const idx = binarySearch(arr, x)
			arr[idx] = Math.min(arr[idx], y)
		}
	}
	return arr.length
}
const binarySearch = (arr, x) => {
	let low = 0,
		high = arr.length - 1
	while (low < high) {
		const mid = low + Math.floor((high - low) / 2)
		if (arr[mid] >= x) {
			high = mid
		} else {
			low = mid + 1
		}
	}

	return low
}
/* 贪心 */
var findLongestChain = function (pairs) {
	let curr = -Number.MAX_VALUE,
		res = 0
	pairs.sort((a, b) => a[1] - b[1])
	for (const p of pairs) {
		if (curr < p[0]) {
			curr = p[1]
			res++
		}
	}
	return res
}
const index = findLongestChain([
	[7, 9],
	[4, 5],
	[7, 9],
	[-7, -1],
	[0, 10],
	[3, 10],
	[3, 6],
	[2, 3],
])
console.log('findLongestChain :>>', index)
